package bfs;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author pengfei.hpf
 * @date 2020/2/17
 * @verdion 1.0.0
 * Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
 *
 * The distance between two adjacent cells is 1.
 *
 *  
 *
 * Example 1:
 *
 * Input:
 * [[0,0,0],
 *  [0,1,0],
 *  [0,0,0]]
 *
 * Output:
 * [[0,0,0],
 *  [0,1,0],
 *  [0,0,0]]
 * Example 2:
 *
 * Input:
 * [[0,0,0],
 *  [0,1,0],
 *  [1,1,1]]
 *
 * Output:
 * [[0,0,0],
 *  [0,1,0],
 *  [1,2,1]]
 *  
 *
 * Note:
 *
 * The number of elements of the given matrix will not exceed 10,000.
 * There are at least one 0 in the given matrix.
 * The cells are adjacent in only four directions: up, down, left and right.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/01-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Matrix01 {
    int[][] dir = new int[][]{{-1,0}, {0, -1}, {1, 0}, {0, 1}};
    public int[][] updateMatrix(int[][] matrix){
        if(matrix == null || matrix.length ==0 || matrix[0].length == 0){
            return matrix;
        }
        int[][] dis = new int[matrix.length][matrix[0].length];
        for(int i = 0 ; i < matrix.length; i ++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < matrix.length; i ++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    dis[i][j] = 0;
                    queue.add(new int[]{i,j});
                }
            }
        }
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            for(int i = 0; i < dir.length; i ++){
                int r = dir[i][0] + cur[0];
                int c = dir[i][1] + cur[1];
                if(r >= 0 && c >= 0 && r < matrix.length && c< matrix[0].length){
                    if(dis[r][c] != 0){
                        if(dis[r][c] > dis[cur[0]][cur[1]] + 1){
                            dis[r][c] =  dis[cur[0]][cur[1]] + 1;
                            queue.add(new int[]{r,c});
                        }
                    }
                }
            }
        }
        return dis;
    }
}
